//插入排序
public class InsertSort
{
    public static void main(String[] args)
    {
        int[] arr = getRandomArray(20);
        for (int i : arr)
        {
            System.out.print(i + " ");
        }
        System.out.println();
        insertSort(arr);
        for (int i : arr)
        {
            System.out.print(i + " ");
        }
    }

    public static int[] insertSort(int[] arr)
    {
        for (int i = 1; i < arr.length; i++)
        {
            int temp = arr[i], j;
            for (j = i; j > 0 && arr[j - 1] > temp; j--)
            {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
        return arr;
    }

    public static int[] getRandomArray(int n)
    {
        int[] arr = new int[10];
        for (int i = 0; i < 10; i++)
        {
            arr[i] = (int) (Math.random() * n + 1);
        }
        return arr;
    }
}
